package com.pandai.leetcode;

public class Solution977 {
    /**
     *      由于数组左右两部分局部都是有序的，采用双指针
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int size = nums.length;
        for(int i=0 ;i<size;i++){
            nums[i] = nums[i] * nums[i];
        }
        int[] arr = new int[size];
        int min=findMinIndex(nums); // min用来记录nums中最小元素的下标
        arr[0] = nums[min];
        int left = min-1;
        int right = min +1;
        // k用来记录新数组处理到哪个元素了
        int k = 1 ;
        while(left>=0 && right <=size -1){
            if(nums[left] <= nums[right]){
                arr[k++] = nums[left];
                left--;
            }else{
                arr[k++] = nums[right];
                right++;
            }
        }
        // 处理剩下一边的元素，注意需要用循环而不是单独的一步
        if(right >= size){
            while(left >=0){
                arr[k++] = nums[left--];
            }
        }
        if(left < 0){
            while(right < size){
                arr[k++] = nums[right++];
            }
        }
        return arr;
    }

    public int findMinIndex(int[] nums){
        // k用来记录nums中最小元素的下标，min用来记录nums中最小的元素值
        int k = 0;
        int min = nums[0];
        for(int i = 1;i<nums.length;i++){
            if(min > nums[i]){
                min = nums[i];
                k = i;
            }
        }
        return k;
    }
}
